package leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

public class P460LfuCache {
    public static void main(String[] args) {
        LFUCache lfu = new P460LfuCache().new LFUCache(2);
        lfu.put(2, 1);
        lfu.put(3, 2);
        System.out.println(lfu.get(2));
        System.out.println(lfu.get(3));
        lfu.put(4, 3); // 2 is the LFU key because cnt(2)=1 is the smallest, invalidate 2. // cache=[3,1], cnt(3)=1, cnt(1)=2
        lfu.put(5, 3); // 2 is the LFU key because cnt(2)=1 is the smallest, invalidate 2. // cache=[3,1], cnt(3)=1, cnt(1)=2
        System.out.println(lfu.get(2)); // return 4 // cache=[4,3], cnt(4)=2, cnt(3)=3
        System.out.println(lfu.get(3)); // return 4 // cache=[4,3], cnt(4)=2, cnt(3)=3
        System.out.println(lfu.get(4)); // return 4 // cache=[4,3], cnt(4)=2, cnt(3)=3
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class LFUCache {
        Map<Integer, Node> map;
        int capacity;
        int size;
        Node tail;

        class Node {
            int val;
            int key;
            int count;
            Node pre;
            Node next;

            public Node(int key, int val) {
                this.val = val;
                this.key = key;
            }
        }


        public LFUCache(int capacity) {
            this.capacity = capacity;
            map = new HashMap<>();
        }

        public void removeOld() {

        }


        public int get(int key) {
            if (!map.containsKey(key)) {
                return -1;
            }
            Node node = map.get(key);
            increment(node);
            moveForward(node);
            return node.val;
        }

        public void increment(Node node) {
            node.count += 1;
        }

        public void addLen() {
            size++;
        }

        public void moveForward(Node node) {
            if (size != 0) {
                Node originPre = node.pre;
                if (originPre == null) {
                    return;
                }
                Node pre = originPre;
                Node cur = null;

                while (pre != null && pre.count <= node.count) {
                    Node prePre = pre.pre;
                    cur = pre;
                    pre = prePre;
                }
                if (pre != originPre) {
                    tail = originPre;
                    Node originNext = node.next;
                    originPre.next = originNext;
                    if (originNext != null) {
                        originNext.pre = originPre;
                    }
                    if (pre != null) {
                        pre.next = node;
                    }
                    node.pre = pre;
                    node.next = cur;
                    if (cur != null) {
                        cur.pre = node;
                    }
                }
            } else {
                tail = node;
            }
        }

        public void put(int key, int value) {
            if (map.containsKey(key)) {
                Node node = map.get(key);
                node.val = value;
                increment(node);
                moveForward(node);
            } else {
                Node node = new Node(key, value);
                increment(node);
                map.put(key, node);
                if (size >= capacity) {
                    Node pre = tail.pre;
                    if (pre != null) {
                        pre.next = node;
                    }
                    node.pre = pre;
                    map.remove(tail.key);
                } else {
                    if (tail != null) {
                        tail.next = node;
                        node.pre = tail;
                    }
                }
                tail = node;
                moveForward(node);
                addLen();
            }

        }
    }

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
//leetcode submit region end(Prohibit modification and deletion)

}